class Trie():
    def __init__(self):
        self.child = {}

    def insert(self, word):
        cur = self.child
        for c in word:
            if c not in cur.keys():
                cur[c] = {}
            cur = cur[c]
        # 结束符
        cur['#'] = '#'

    def search(self, word):
        cur = self.child
        for c in word:
            if c not in cur.keys():
                return False
            cur = cur[c]
            if '#' not in cur.keys():
                return False
        return True


def longestWord(words):
    words.sort()
    res = ''
    trie = Trie()
    max_len = 0
    for word in words:
        trie.insert(word)
    for word in words:
        if trie.search(word) and len(word) > max_len:
            res = word
            max_len = len(word)
    return res


words = ["a", "banana", "app", "appl", "ap", "apple", "apply"]
print(longestWord(words))
